\documentclass[]{article}
\usepackage{xeCJK}
\setCJKmainfont{Noto Serif CJK TC}
\usepackage[a4paper]{geometry}
\usepackage{setspace}
\onehalfspacing
\usepackage{float}
\usepackage{amsmath}
\usepackage{graphicx} 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}

\begin{center}
\Huge \textbf{数值分析第四次理论作业} \\ [0.2cm]
\LARGE 林敬翊 3210300367 信息与计算科学

\end{center}
\section{QI}
$$x=\pm m \times\beta^e,\beta=2$$
$$477=2^8+2^6+0+2^4+2^3+2^2+0+2^0$$
$$e=8,m=\frac{477}{2^8}=(1.11011101)_{2} \times 2^8$$
\section{QII}
$$x=\pm m \times\beta^e,\beta=2$$
$$\frac{3}{5}=2^{-1}+0+0+2^{-4}+2^{-5}+0+0+2^{-8}+...$$
$$e=-1,m=(1.00110011...)_{2}$$
$$\frac{3}{5}=(0.10011001...)_{2}=(1.0011001...)_{2} \times 2^{-1}$$

\section{QIII}
证明$x=\beta^e=(1.00...00)_{\beta} \times \beta^e$, 其中$m=(1.000...00)_{\beta}$保留p位有效数字，$x_L,x_R$与$x$相邻, $x_L<x<x_R$
$$x_L=(d.dd ... dd)_{\beta}\times \beta^{e-1}$$其中$d=\beta -1$
$$x_R=(1.00 ... 01)_{\beta} \times \beta^e$$其中$m_L$和$m_R$均保留p位有效数字
$$x_R-x=(0.00 ... 01)_{\beta} \times \beta^e=1 \times \beta^{1-p}\times \beta^e = \beta^{e+1-p}$$
$$x-x_L=(0.00 ... 01)_{\beta} \times \beta^{e-1} = 1 \times \beta^{1-p} \times \beta^{e-1} = \beta^{e-p}$$
$$x_R-x=\beta(x-x_L)$$
\section{QIV}
根据IEEE 754 single-precision protocol保留$p=23+1$有效数字
$$\frac{3}{5}=(0.100110011001100110011001...)_{2}=(1.00110011001100110011001...)_{2} \times 2^{-1}$$
记$x_L,x_R$与$x$相邻，$$x_L < x < x_R$$
$$x_L=(1.00110011001100110011001)_{2} \times 2^{-1}$$

$$
x_R=(1.00110011001100110011010)_{2} \times 2^{-1}
$$
$$
x-x_L=\frac{3}{5} \times 2^{-24},x_R-x_L=2^{-24},x_R-x=(x_R-x_L)-(x-x_L)=\frac{2}{5}\times 2^{-24}
$$
根据定义4.24 $fl(x)=x_R$
相对舍入误差$\varphi=\frac{|fl(x)-x|}{|x|}=\frac{2}{3}\times 2^{-24}$
\section{QV}
根据IEEE 754 single-precision protocol，直接截断多余的值
$$|fl(x) \leq |x_R-x_L| \leq \varepsilon_M min(|x_R|,|x_L|)< \varepsilon_M|x|$$
$$\varepsilon_u = \varepsilon_M= \beta^{1-p}=2^{-23} \approx 1.19\times 10^-7$$
\section{QVI}
记$x=1,y=cos\frac{1}{4} \rightarrow x,y\in\mathcal{F}$\\
根据定理4.49，$\beta^{-t}\geq 1-\frac{y}{x}=1-\frac{cos\frac{1}{4}}{1}\geq\beta^{-5}$\\
取$\beta=2 \rightarrow 2^-6\geq 1- \frac{cos\frac{1}{4}}{1}\geq 0.03109\geq 2^{-5} \rightarrow t=6,s=5$\\
$\rightarrow$ 减法运算$1-cosx$，当$x=\frac{1}{4}$时损失6位精度  
\section{QVII}
1.利用泰勒展开：
$$
cosx=1-\frac{x^2}{2!}+\frac{x^4}{4!}-\frac{x^6}{6!}+.....
$$
$$
1-cosx=\frac{x^2}{2!}-\frac{x^4}{4!}+\frac{x^6}{6!}+....
$$
2.利用二倍角公式
$$
1-cosx=2sin^2\frac{x}{2}
$$
方法1 : $1-cosx=\frac{x^2}{2!}-\frac{x^4}{4!}+\frac{x^6}{6!}+....+(\frac{x^{4n}}{(4n-2)!}-\frac{x^{4n}}{(4n)!})+....$
取$\frac{x^{4n}}{(4n-2)!}-\frac{x^{4n}}{(4n)!}$
当$x \rightarrow0,x>0$，此时$1-cosx \rightarrow 0 $,根据Example 4.48,利用泰勒公式展开，再由定理4.49
$$
2^{-1} \leq 1 - \frac{\frac{x^{4n}}{(4n)!}}{\frac{x^{4n-2}}{(4n-2)!}}=1-\frac{x^2}{4n(4n-1)}\leq 2^0
$$
方法2: $1-cosx=2sin^2\frac{x}{2}$

\section{QVIII}
1.$f(x)=(x-1)^{\alpha}$,当$\alpha=0,f(x)=1,C_{f}(x)=0$\\
当$\alpha \neq0,C_f(x)=|\frac{xf^{'}x}{f(x)}|=|\frac{x \cdot \alpha(x-1)^{\alpha -1}}{(x-1)^{\alpha}}|=|\frac{\alpha x}{x-1} |,x\rightarrow1,C_f(x)\rightarrow +\infty$\\
2.$f(x)=lnx,C_f(x)=|\frac{xf^{'}(x)}{f(x)}|=|\frac{x\cdot\frac{1}{x}}{lnx}|=|\frac{1}{lnx}|,x\rightarrow1,C_{f}(x)\rightarrow+\infty$\\
3.$f(x)=e^x,C_f(x)=|\frac{xf^{'}(x)}{f(x)}|=|\frac{x\cdot e^x}{e^x}|=|x|,x\rightarrow \pm \infty,C_f(x)\rightarrow + \infty$\\
4.$f(x)=arccosx,C_f(x)=|\frac{xf^{'}(x)}{f(x)}|=\frac{x\cdot\frac{-1}{\sqrt{1-x^2}}}{arccosx}=|\frac{x}{\sqrt{1-x^2}arccosx}|,x\rightarrow\pm1,C_{f}(x)\rightarrow + \infty$


\section{QIX}
\subsection{1}
证明$cond_f(x)=C_f(x)=|\frac{xf^{'}x}{f(x)}|=|\frac{x\cdot e^{-x}}{1-e^{-x}}|\frac{x}{e^x-1}|$\\
$x\in(0,1],e^x-1>x \rightarrow cond_f(x)<1$\\
$x=0,cond_f(0)=lim_{x\to 0}|\frac{x}{e^x-1}|=1$\\
$\rightarrow x \in[0,1],cond_f(x)\leq1$
\subsection{2}
$$
f_A(x)=fl(1-fl(e^{-x})=[1-e^{-x}(1+\delta_1)](1+\delta_2),
$$
$$
f_A(x)=[(1-e^{-x}(1+\delta_1)](1+\delta_2)=(1-e^{-x})(1+\delta_2)-e^{-x}\delta_1(1+\delta_2)
$$
$$
=(1-e^{-x})[1+\delta_2-\delta_1(1+\delta_2)\frac{e^{-x}}{1-e^{-x}}]\approx(1-e^{-x})(1+\delta_2-\delta_1\frac{e^{-x}}{1-e^{-x}})
$$
$$
\delta (x)=\delta_2-\delta_1\frac{e^{-x}}{1-e^{-x}}
$$
有$\varphi(x)=1+\frac{e^{-x}}{1-e^{-x}}=\frac{1}{1-e^{-x}}=\frac{e^{x}}{e^{x}-1}$

$$
x \in \mathcal{F},cond_A(x)\leq \frac{\varphi(x)}{cond_f(x)} = \frac{e^x}{e^x-1}\cdot|\frac{e^x-1}{x}|=\frac{e^x}{x}
$$
得出结论$cond_A(x)\leq\frac{e^x}{x}$,其中$x \in [0,1]$
\subsection{3}
\begin{figure}[H]
    \centering
    \includegraphics[scale=0.4]{图10.jpg}
\end{figure}
从上面的图片中，我们可以看出函数 \( f \) 的条件数从 1 减小到 \( \frac{1}{e} \) 是单调递减的。这意味着如果 \( x \) 发生变化，\( f(x) \) 不会有太大的变化。通过 \( f(x) \) 的图像可以合理地看出这一点。此外，当 \( x \) 接近 0 时，算法的条件数极大。这意味着如果我们用机器计算接近 0 的 \( f(x) \)，会产生很大的误差。

\section{QX}
 \subsection*{证明}
考虑一个归一化的浮点数系统(FPN)的范围，它是实数 $\mathbb{R}$ 的一个子集，由两个区间组成：
\[
\mathcal{R}(\mathcal{F}):=\{x: x \in \mathbb{R}, \operatorname{UFL}(\mathcal{F}) \leq |x| \leq \operatorname{OFL}(\mathcal{F})\}
\]

假设 $r$ 是多项式 $q(x)=\sum_{i=0}^{n}a_ix^i$ 的根，其中 $a_n=1, a_0\neq 0, a_i\in \mathbb{R}$，考虑向量范数 $f:\mathbb{R}^n\to \mathbb{C}$，其中 $r=f(a_0, a_1, \cdots, a_{n-1})$。基于 1 范数，条件数定义为：
\[
cond_f(x) = \frac{\|x\| \|\nabla f\|}{\|f(x)\|} = \frac{1}{|r|} \sum_{i=0}^{n-1} |a_i \frac{\partial r}{\partial a_i}|
\]
其中 $x=(a_0, a_1, \cdots, a_{n-1})$。

由于 $r$ 是 $q(x)$ 的根，我们有 $q(r) = 0$，即：
\[
q(r) = \sum_{i=0}^{n} a_i r^i = r^n + a_{n-1}r^{n-1} + \dots + a_1r + a_0 = 0
\]
对每个 $a_i$ 求偏导数，得：
\[
\Rightarrow nr^{n-1} \frac{\partial r}{\partial a_i} + a_{n-1}(n-1)r^{n-2} \frac{\partial r}{\partial a_i} + \cdots + r^i + a_i i r^{i-1} \frac{\partial r}{\partial a_i} + \cdots + a_1 \frac{\partial r}{\partial a_i} + 0 = 0
\]
进一步化简，得：
\[
\Rightarrow \frac{\partial r}{\partial a_i} = -\frac{r^i}{q'(r)}, \quad i = 0, 1, \cdots, n-1
\]
因此，条件数可表示为：
\[
\begin{aligned}
\Rightarrow cond_f(x) &= \frac{1}{|r|} \sum_{i=0}^{n-1} |a_i \frac{\partial r}{\partial a_i}| \\
&= \frac{1}{|r|} \sum_{i=0}^{n-1} \left| a_i \left(-\frac{r^i}{q'(r)}\right) \right| \\
&= \frac{1}{|r q'(r)|} \sum_{i=0}^{n-1} |a_i r^i|
\end{aligned}
\]

对于 Wilkinson 示例，设 $p(x) = \prod_{k=1}^{n}(x-k) = \sum_{i=0}^{n} a_i x^i$，条件数可表示为：
\[
cond_f(x) = \frac{\prod_{k=1}^{n}(r+k) - r^n}{|r \sum_{i=1}^{n} \prod_{k=1,k \neq i}^{n}(r-k)|}
\]
当根 $r = n$ 时，条件数为：
\[
\begin{aligned}
\Rightarrow cond_f(x) &= \frac{\prod_{k=1}^{n}(n+k) - n^n}{n!} \\
&= \frac{\prod_{k=1}^{n}\left(1 + \frac{k}{n}\right) - 1}{n} \frac{n^n}{(n-1)!} \geq \frac{n^n}{n!}
\end{aligned}
\]
因此，当 $n \to +\infty$ 时，$cond_f(x) \to +\infty$，说明当多项式的次数非常高时，即使是微小的扰动也会导致根的显著变化，这表明高次数的多项式的寻根问题难以解决。

\section{QXI}

考虑多项式
\[
q(x)=\sum_{i=0}^{n} a_{i} x^{i}, \quad a_{n}=1, a_{0} \neq 0, a_{i} \in \mathbb{R}
\]
可以视为向量函数 $f: \mathbb{R}^{n} \rightarrow \mathbb{C}$:
\[
r=f\left(a_{0}, a_{1}, \ldots, a_{n-1}\right).
\]
基于 1-范数导出 $f$ 的逐元素条件数。对于 Wilkinson 示例，计算你的条件数，并与 Wilkinson 示例中的结果进行比较。比较告诉你什么？

\subsection*{FPN 系统 $(\beta,p,L,U)$ 示例}
不妨取 $\beta=2, p=2, L=-1, U=1$，即 (2,2,-1,1)。设 $a, b \in F$，取 $a=2=(1.0)_2\times2^1, b=3=(1.1)_2\times2^1, c=fl(\frac{a}{b})$，其中寄存器精度为 $2p=4$。

\begin{enumerate}
    \item $(i)$ $e_c = e_a - e_b = 0$。
    \item $\to (ii)$ $M_c = \frac{M_a}{M_b} = \frac{(1.0)_2}{(1.1)_2} = (0.101)_2$。
    \item $\to (iii)$ $|M_c| < 1 \Rightarrow M_c = M_c\beta = (1.01)_2, e_c = e_c - 1 = -1$。
    \item $\to (iv)$ $e_c \in [L, U]$。
    \item $\to (v)$ $M_c = (1.0)_2$。
    \item $\to (vi)$ $c = M_c \times \beta^{e_c} = (1.0)_2 \times 2^{-1}$。
\end{enumerate}
\[
\Rightarrow c = fl\left(\frac{a}{b}\right) = fl\left(\frac{2}{3}\right) = (1.0)_2 \times 2^{-1}。
\]
根据 Lemma 4.39:
\[
fl\left(\frac{a}{b}\right) = \frac{a}{b}(1 + \delta)。
\]
\[
\Rightarrow \delta = \frac{fl\left(\frac{a}{b}\right) - \frac{a}{b}}{\frac{a}{b}} = \frac{fl\left(\frac{2}{3}\right) - \frac{2}{3}}{\frac{2}{3}} = -\frac{(0.01010\cdots)_2 \times 2^{-1}}{(1.01010\cdots)_2 \times 2^{-1}} = -\frac{1}{4}。
\]
\[
|\delta| = \frac{1}{4} = \frac{1}{2}\beta^{1-p} = \epsilon_u。
\]
但这与 $|\delta| < \epsilon_u$ 的假设矛盾！

\section{QXII}

考虑 IEEE 754 单精度协议的浮点数系统 \(FPN_s\)。假设我们使用二分法计算根 \(r = m \times \beta^e\)，其中 \(r\) 在区间 \([128, 129]\)，底数 \(\beta = 2\)。

\begin{itemize}
    \item 由于 \(r\) 在给定区间内，可以推断出 \(e = 7\)，精度 \(p = 23 + 1\)（IEEE 754 单精度浮点数有 23 位尾数和 1 位隐藏位）。
    \item 因此，绝对精度 \(\Delta\) 为 \(\epsilon_M \cdot \beta^e = \beta^{1-p} \cdot \beta^e = 2^{-16}\)，这大于 \(10^{-6}\)。
    \item 结果表明，无法以小于 \(10^{-6}\) 的绝对精度计算根。
\end{itemize}

这个示例展示了在给定的浮点数系统和计算方法下，可能无法达到预期的精度水平，这与机器算术的模型预期的结论相矛盾。
\section{QXIII}


考虑在 IEEE 754 单精度浮点数系统中使用二分法，起始区间为 \([128, 129]\)，探讨是否可以计算出绝对精度小于 \(10^{-6}\) 的根。

通过三次样条拟合曲线，记 \(s(f; x_i) \in S_{3}^{2}\)，其中 \(i = 1, 2, \ldots, N\)。当两个相邻节点 \(x_k, x_{k+1}\) 的距离远小于其他节点的距离时，根据引理 3.3，我们有：
\[
\mu_i = \frac{x_i - x_{i-1}}{x_{i+1} - x_{i-1}}, \quad \lambda_i = \frac{x_{i+1} - x_i}{x_{i+1} - x_{i-1}}, \quad i = 2, 3, \ldots, N-1。
\]
对函数 \(f\) 进行插值，需要求解 \(Am = b\)，其中 \(m = (m_2, \cdots, m_{N-1})^{T}\)，且 \(m_i = s'(f; x_i)\)。

系数矩阵 \(A\) 为：
\[
A =
\begin{pmatrix}
2 & \mu_2 & & & & \\
\lambda_3 & 2 & \mu_3 & & & \\
 & \ddots & \ddots & \ddots & \\
 & & \ddots & \ddots & \mu_{N-2} \\
 & & & \lambda_{N-1} & 2 \\
\end{pmatrix}。
\]
当 \(|x_k - x_{k-1}| \to 0\) 时，\(\lambda_k \to 0, \mu_{k+1} \to 0\)。

条件数 \(cond_f(x) = \frac{\|b\| \, \|A^{-1}\|}{\|m\|} = \frac{\|Am\| \, \|A^{-1}\|}{\|m\|}\)。

最大条件数 \(cond_f(x) = \|A\| \, \|A^{-1}\| = condA\)。

当 \(\lambda_k \to 0, \mu_{k+1} \to 0\) 时，\(\|A^{-1}\| \to +\infty\)，因此 \(condA \to +\infty\)。

这表明当两个相邻节点的距离极小时，该问题是病态的，存在较大的误差，导致插值结果不准确。

\end{document}
